#pragma once
#include <iostream>
#include <vector>
#include <string>
#include <utility>


template<class K>
struct defaultHashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

template<>
struct defaultHashFunc<std::string>
{
	size_t operator()(const std::string& str)
	{
		//BKDR 算法
		size_t ret = 0;
		for (auto ch : str)
		{
			ret = ret * 131 + ch;
		}
		return ret;
		//return (size_t)str[0];
	}
};

namespace open_addr
{
	enum STATE
	{
		EXIST, // 当前位置存在值
		DELETE, //位置值已删除 
		EMPTY //当前位置为空
	};


	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv; // 数据
		STATE _state = EMPTY; // 状态
	};

	//struct stringHashFunc
	//{
	//	size_t operator()(const string& str)
	//	{
	//		return (size_t)str[0];
	//	}
	//};


	template<class K, class V, class HashFunc = defaultHashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_hashTable.resize(10);
		}

		bool insert(const pair<K, V>& kv)
		{
			//维持key的唯一性
			if (find(kv.first))
				return false;
			//扩容逻辑
			//if ((double)_n / _hashTable.size() >= 0.75)
			if (_n * 10 / _hashTable.size() >= 7)

			{
				//创建新表
				size_t newSize = _hashTable.size() * 2;
				HashTable<K, V, HashFunc> newTable;
				newTable._hashTable.resize(newSize);

				//将旧表的数据插入到新表
				for (size_t i = 0; i < _hashTable.size(); i++)
				{
					if (_hashTable[i]._state == EXIST)
						newTable.insert(_hashTable[i]._kv);//复用当前insert的线性探测逻辑
				}

				_hashTable.swap(newTable._hashTable);//类似于拷贝构造之前的现代写法
			}

			//线性探测
			HashFunc func;
			size_t hashI = func(kv.first) % _hashTable.size(); // % capacity()可能会导致[]访问的越界

			while (_hashTable[hashI]._state == EXIST)//EXIST状态表示当前位置值有效
			{
				++hashI;

				hashI %= _hashTable.size(); //当遍历到最后一个位置没法插入，得回到起始位置再匹配。
			}

			//插入值并修改状态
			_hashTable[hashI]._kv = kv;
			_hashTable[hashI]._state = EXIST;
			++_n;

			return true;
		}

		HashData<const K, V>* find(const K& key)
		{
			//线性探测
			HashFunc func;
			size_t hashi = func(key) % _hashTable.size();

			while (_hashTable[hashi]._state != EMPTY)
			{
				if (_hashTable[hashi]._state == EXIST
					&& _hashTable[hashi]._kv.first == key)
				{
					//强转保证可移植性
					return (HashData<const K, V>*) & _hashTable[hashi]._kv;
				}

				++hashi;
				hashi %= _hashTable.size();
			}

			return nullptr;
		}

		bool erase(const K& key)
		{
			HashData<const K, V>* ret = find(key);

			if (ret)
			{
				ret->_state = DELETE;
				--_n;

				return true;
			}
			return false;
		}


	private:
		vector<HashData<K, V>> _hashTable;
		size_t _n = 0; // 记录当前有效元素个数，计算负载因子
	};
}

namespace hash_bucket
{
	template<class T>
	struct hashNode
	{
		T _data;
		hashNode<T>* _next;

		hashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	//前置声明，避免编译报错。声明模板可以不带默认参数
	template<class K, class T, class KeyOfT, class HashFunc>
	class HashTable;

	template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
	struct HTIterator
	{
		typedef hashNode<T> Node;
		typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
		typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;

		Node* _node;
		const HashTable<K, T, KeyOfT, HashFunc>* _ptable; // 为了兼容const迭代器，将对象变成const对象

		//HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pt)
		//	:_node(node)
		//	, _ptable(pt)
		//{}

		// 参数为普通迭代器时，就是普通迭代器的拷贝构造
		// 参数为const迭代器时，就是普通迭代器构造const迭代器的特殊构造
		HTIterator(const iterator& it)
			:_node(it._node)
			, _ptable(it._ptable)
		{}

		HTIterator(Node* node, const HashTable<K, T, KeyOfT, HashFunc>* pt)
			:_node(node)
			, _ptable(pt)
		{}

		T& operator*()
		{
			return _node->_data;
		}

		T* operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

		bool operator==(const Self& s)
		{
			return _node == s._node;
		}

		Self& operator++()
		{
			if (_node->_next)//当前Node不处于链表尾部
			{
				_node = _node->_next;
			}
			else//处于链表尾部
			{
				HashFunc hf;
				KeyOfT kot;
				//计算哈希值
				size_t hashi = hf(kot(_node->_data)) % _ptable->_table.size();
				++hashi;

				//遍历剩余的表，看看有没有节点
				while (hashi < _ptable->_table.size())
				{
					if (_ptable->_table[hashi])
					{
						_node = _ptable->_table[hashi];
						return *this;
					}
					else
					{
						++hashi;
					}
				}

				_node = nullptr;
			}

			return *this;
		}
	};

	template<class K, class T, class KeyOfT, class HashFunc = defaultHashFunc<K>>
	class HashTable
	{
		typedef hashNode<T> Node;

		template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
		friend struct HTIterator; // 定义友缘模板，让HTIterator可以访问HashTable的私有成员

	public:
		typedef HTIterator< K, T, T*, T&, KeyOfT, HashFunc> iterator;
		typedef HTIterator< K,  T, const T*, const T&, KeyOfT, HashFunc> const_iterator; 

		iterator begin()
		{
			//找第一个节点
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				if (cur != nullptr)
				{
					return iterator(cur, this);
				}
			}
			return iterator(nullptr, this);
		}

		iterator end()
		{
			return iterator(nullptr, this);
		}

		const_iterator begin() const
		{
			//找第一个节点
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];
				if (cur != nullptr)
				{
					return const_iterator(cur, this);
				}
			}
			return const_iterator(nullptr, this);
		}

		const_iterator end() const
		{
			return const_iterator(nullptr, this);
		}

		HashTable()
		{
			_table.resize(10, nullptr);//给桶一个初始值
		}

		HashTable(const HashTable<K, T, KeyOfT, HashFunc>& HT)
		{
			_table.resize(HT._table.size());
			for (int i = 0; i < HT._table.size(); i++)
			{
				Node* cur = HT._table[i];

				while (cur)
				{
					Node* newn = new Node(cur->_kv);//创建新节点
					newn->_next = _table[i];//将原头节点连接到新节点的后面
					_table[i] = newn; //覆盖原头节点的位置
					++_n;

					cur = cur->_next;//迭代
				}
			}
		}


		~HashTable()
		{
			//遍历桶，依次删除节点
			for (int i = 0; i < _table.size(); i++)
			{
				Node* cur = _table[i];

				while (cur)
				{
					Node* next = cur->_next;
					delete cur;
					cur = next;
				}

				cur = nullptr;
			}
		}

		pair<iterator, bool> insert(const T& data)
		{
			HashFunc hf;
			KeyOfT kot;

			iterator it = find(kot(data));
			if (it != end())
				return make_pair(it, false);

			//扩容
			//...
			if (_n == _table.size())
			{
				size_t newSize = _table.size() * 2;// 2倍扩容
				HashTable<K, T, KeyOfT, HashFunc> newTable; //创建新表
				newTable._table.resize(newSize, nullptr);//将空间扩容后，初始化成空

				//依次将旧表节点链接到新表
				for (int i = 0; i < _table.size(); i++)
				{
					Node* cur = _table[i];

					while (cur)
					{
						Node* next = cur->_next;//记录下一跳节点
						size_t hashi = hf(kot(data)) % newSize;//映射哈希值

						cur->_next = newTable._table[hashi];//将原头节点连接到新节点的后面
						newTable._table[hashi] = cur; //覆盖原头节点的位置

						cur = next; //迭代
					}
					_table[i] = nullptr;//置空原表
				}
				_table.swap(newTable._table);//将新表跟旧表交换一下。
			}

			//插入数据
			size_t hashi = hf(kot(data)) % _table.size();

			Node* newn = new Node(data);//创建新节点
			newn->_next = _table[hashi];//将原头节点连接到新节点的后面
			_table[hashi] = newn; //覆盖原头节点的位置

			++_n;
			return make_pair(iterator(newn, this), true);
		}


		//维持key的唯一性
		iterator find(const K& key)
		{
			HashFunc hf;
			KeyOfT kot;
			//获取哈希值
			size_t hashi = hf(key) % _table.size();

			//遍历链表
			Node* cur = _table[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return iterator(cur, this);
				}
				cur = cur->_next;
			}
			return end();
		}

		bool erase(const K& key)
		{
			HashFunc hf;
			size_t hashi = hf(key) % _table.size();

			Node* prev = nullptr;
			Node* cur = _table[hashi];

			while (cur)
			{
				if (cur->_kv.first == key && prev == nullptr) //头删
				{
					_table[hashi] = cur->_next;
					delete cur;
					cur = nullptr;
					return true;
				}
				else if (cur->_kv.first == key) //中间删除/尾删
				{
					Node* next = cur->_next;
					prev->_next = next;
					delete cur;
					cur = nullptr;
					return true;
				}

				prev = cur;
				cur = cur->_next;
			}
			return false;
		}


		void Print()
		{
			for (int i = 0; i < _table.size(); i++)
			{
				printf("[%d]", i);
				cout << "->";
				Node* cur = _table[i];
				while (cur)
				{
					cout << cur->_kv.first << " : " << cur->_kv.second << " -> ";
					cur = cur->_next;
				}
				cout << "NULL" << endl;
			}
			cout << endl;
		}


	private:
		vector<Node*> _table; //哈希桶
		size_t _n = 0; // 记录数据个数
	};
}
